// 1.重复-217-是否有重复元素 完成：1\1
// 2.重复-219-是否有重复元素2 完成：1\1
// 3.异位-242-字母异位  完成：1\1
// 4.异位-49-字母异位分组    完成：1\1
// 5.回文-409-最长回文长度    完成： 1\1
// 6.交集-349-两个数组的交集  完成：1\1
// 7.求和-1-两数之和  完成：1\1
// 8.无重复子串-3-最长无重复子串 完成：1\1
// 9.连续序列-128-最长连续序列  完成：1\1
// 10.和为k的子串- 560-（连续）- 前缀和问题 完成：1\1
// 11.238-除自身外的乘积 1\1
// 12.146-LRU缓存 完成：1\1


// 1.是否有重复元素
// 题解：判断字符串中是否有重复的元素
// 思路：借助map，循环，map中存在当前元素，返回ture，不存在map set当前元素
// 注意点： set key是元素，val是true
var hasDubbleKey = (str) => {
  let map = new Map();
  for (let i = 0; i < str.length; i++) {
    if (map.has(str[i])) {
      return true
    } else {
      map.set(str[i], true)
    }
  }
  return false
}
console.log(hasDubbleKey("aca"))

// 2.是否有重复元素2
// 题解：是否有两个元素 str[i] === str[j] 并且i-j < k ，判断条件不止相等还有，索引差值<k
// 思路：利用lru的思想，当空间大于k时，则会移除最前面的数字，则存在在这个范围内的元素都符合要求
// 注意：set 不重复性并不会影响，如果重复前置的判断条件已经返回true，当做一个数组就可以
var hasDubbleKey2 = (str, k) => {
  let set = new Set();
  for (let i = 0; i < str.length; i++) {
    if (set.has(str[i])) { // 如果set内存在，肯定i-j < k, 因为超出k会把之前的删除类似LRU
      return true
    }
    set.add(str[i])
    if (set.size > k) {
      set.delete(str[i-k])
    }
  }
  return false
}
console.log(hasDubbleKey2('acacs', 2))

// 3.字母异位
// 题解：判断两个字符串是否是有效的字母异位 元素一一对应，只是顺序乱了
// 思路：利用一个map维护状态，循环其中一个数组，每个位置先判断s1元素是否存在，不存在则赋值1，存在则数量++；借着判断s2, 不存在-1，存在--；
// 注意：两两抵消后，Object.values(map)转换为数组，最后every 判断每个必须val为0
var hasSameWord = (s1, s2) => {
  if (s1.length !== s2.length) return false
  let map = {};
  for (let i = 0; i < s1.length; i++) {
    map[s1[i]] ? map[s1[i]]++ : map[s1[i]] = 1;
    map[s2[i]] ? map[s2[i]]-- : map[s2[i]] = -1;
  }
  return Object.values(map).every(v => v === 0)
}
console.log(hasSameWord("jiao", "oaij"))

// 4.字母异位分组
// 题解：将异位词分组，变位一个二维数组
// 思路：map维护状态，key是排序后的相同项，value是结果数组，存在则push后set；不存在则set新数组
// 注意：sort() 可直接字母排序，map.values() 获取结果数组
var groupAnagrams = (arr) => {
  let map = new Map()
  for (let i = 0; i < arr.length; i++) {
    let str = arr[i].split('').sort().join('');
    if (map.has(str)) {
      let temp = map.get(str)
      temp.push(arr[i])
      map.set(str, temp)
    } else {
      map.set(str, [arr[i]])
    }
  }
  return [...map.values()];
}
console.log(groupAnagrams(['aca', 'aac']))

// 5.最长回文长度
// 题解：自己构造一个回文，返回回文长度，不需要顺序
// 思路：存在相同则说明可构造一组回文，长度+2，并删除原有；不存在相同则添加到set
// 注意：如果set内还有元素，则可构造成奇数回文，长度+1
var maxLongString = (s) => {
  let temp = new Set();
  let max = 0;
  s.split('').forEach(c => {
    if (temp.has(c)) {
      max += 2
      temp.delete(c)
    } else {
      temp.add(c)
    }
  })
  return max + (temp.size > 0 ? 1 : 0) // temp 还有元素，则可以拼接一个奇数的回文
}
console.log(maxLongString("acasdad"))
// 思考分类：
// 1. 是否是回文（array-两边夹逼）
// 2. 最长回文长度（乱序）（map 存在+2）
// 3. 最长回文子串（连续 array中心扩散）最长回文子序列（不连续，但有先后 dp 二维倒序，相等+2， 不相等取 上右 ）【TODO】
// 5. 回文的回文子串 （数目 dp）【TODO】
// 4. 是否是回文链表（link -转换为数组）


// 6.两个数组的交集
// 题解：两个数组的交集，输出元素唯一
// 思路：找出最长数组遍历，短的转换为set，set2保存结果，循环长数组，如果短set内存在，则是交集放入结果set
// 注意：set 自动去了重复
var intersection = (nums1, nums2) => {
  if (nums1.length < nums2.length) {
    [nums2, nums1] = [nums1, nums2]
  }
  let num1Set = new Set(nums1);
  let resSet = new Set();
  for (let i = nums2.length - 1; i >= 0; i--) {
    num1Set.has(nums2[i]) && resSet.add(nums2[i])
  }
  return Array.from(resSet)

  // return [...new Set(nums1.filter((item) => {
    //     return nums2.includes(item)
    // }))]
}
console.log(intersection(nums1 = [1, 2, 2, 1], nums2 = [2, 2]))

// 7.两数之和
// 题解：找出一种两数之和为target的情况，返回索引
// 思路：判断map[target-nums[i]]是否存在；存在则返回[map[target-nums[i]], i]
// 注意：返回索引
var twoSum = (nums, target) => {
  let hash = {};
  for (let i = 0; i < nums.length; i++) {
    if (hash[target - nums[i]] !== undefined) {
      return [hash[target - nums[i]], i]
    }
    hash[nums[i]] = i
  }
  return []
}
console.log(twoSum(nums = [2, 7, 11, 15], target = 9))
// 思考分组：
// 1. 两数之和（map）
// 2. 三数之和 四数之和（array） 【TODO】
// 3. 组合之和1，组合之和2，组合之和3（backtracing）【TODO】

// 8.最长无重复子串 - 更多是一种滑动窗口的方式
// 题解：找出这个字符串里不重复的最长子串（子串要求连续）
// 思路：map作为存储状态，left 为相同字符下一个最远位置，出现相同则缩小窗口，左边全部删除长度，// 计算right在每个位置的最长不重复子串，尽可能的扩大窗口，比较max最大值
// 注意：left 和 max 都是一个暂存状态，需要Math.max比较，map维护的每个字符的下一个位置（left）
var lengthOfLongestSubstring = (s) => {
  let map = new Map();
  let max = 0;
  let left = 0;
  for (let right = 0; right < s.length; right++) {
    if (map.has(s[right])) { // 存在重复， 相同字符的下一个位置
      left = Math.max(map.get(s[right]) + 1, left)
    }
    max = Math.max(max, right - left + 1)  // 出现相同则缩小窗口，左边的全部删除
    map.set(s[right], right)
  }
  return max
}

// 9.最长连续上升序列
// 题解：找出这个无序数组中的最长连续数，目标在原数组中不要求连续
// 思路：set 作为状态存储，如果他的他的前一个连续不存在，则判断为这个为连续的起始点；while 一直找下一个，计算count++；max 为此循环中count 与历史max的最大值
// 注意：先去重
var longestConsecutive = (nums) => {
  const set = new Set(nums); // 去重
  let max = 0;
  for (let [_, v] of set.entries()) {
    // 判断之前一个是否存在
    if (!set.has(v - 1)) { // 当前节点必为起点，减少循环
      let j = 1;
      while (set.has(v + 1)) { // 一直寻找下一个是否存在
        j++
      }
      max = Math.max(j, max)
    }
  }
  return max
}
console.log(longestConsecutive([100, 4, 200, 1, 3, 2]))

// 10.和为k的子串（连续）- 前缀和问题
// 题解：sum(i,j) = k i到j之间的和是k； sum(0, j) 循环当前的prefixSum，sum(0, i-1)只存了结果【map(2)=2: 表示2出现了两次，如果[1,1,0,3], i可能在2,3索引处】之前出现的前缀和prefixSum，并未存i，结果就是不同i的可能次数
// 思路：sum(i,j) = k 转换为 sum(0, j) - k = sum(0, i - 1)则转换为了前序和问题 当计算到j时，【sum(0, j) - k】的值之前是否存在过，存在则子串数量增加，值则是不同i的可能次数
// 注意：一定要初始化{0: 1} 代表prefixSum 0出现了一次
const subArrSum = (nums, k) => {
  const map = { 0: 1 }; // value 前缀和出现的次数。(因为可能出现0，负数，所以前缀和可能重复)
  let prefixSum = 0;
  let count = 0;
  for (let j = 0; j < nums.length; j++) {
    prefixSum += nums[j];
    if (map[prefixSum - k]) { // perfixSum - k 就是 i-1
      count += map[prefixSum - k]
    }

    if (map[prefixSum]) {
      map[prefixSum]++
    } else {
      map[prefixSum] = 1
    }
  }
  return count
}
// 思考分组：贪心-map-dp
// 判断
// 1.是否是子序列 (greedy)
// 单个-最长
// 1. 最长无重复子串（连续）（map）
// 3. 最长连续上升序列（不连续结果连续）（map）
// 4. 最长上升子串（连续结果不连续）（greedy）
// 5. 最长上升子序列（不连续结果也不连续）（dp）
// 多个-公共最长
// 4. 最长公共子序列 /最长公共子串（多个）（dp）
// 求和
// 2. 和为k的子串（连续）（map-前缀和） 和为k的子序列
// 6. 最大子串和 （greedy - 判断递增循环）


// 11. 除自身外的乘积 （有点类似前缀和） 
// 题解：数组内除自身外的乘积
// 思路：
var productExceptSelf = function(nums) {
  let left = []; // 每个索引之前的乘积
  let right = []; // 每个索引之后的乘积
  let res = []; // 结果就是 left[i-1] * right[i+1] 注意两边的边界情况

  left[0] = nums[0]
  for(let i = 1; i< nums.length; i++){
      left[i] = left[i-1] * nums[i]
  }

  right[nums.length -1] = nums[nums.length -1]
  for(let i = nums.length - 2; i >= 0; i--){
      right[i] = right[i+1] * nums[i]
  }

  for(let i =0; i< nums.length; i++){
      if(i === 0){
          res[i] = right[i+1]
      } else if(i === nums.length -1){
          res[i] = left[i-1]
      } else {
          res[i] = left[i-1] * right[i+1]
      }
  }
  return res
};



// 12.LRU缓存
// 题解：get后要将其放在队列后，put 超出容量要删除队列头
// 思路：超出容量删除，get 先删后加，map自带顺序
// 注意：使用的是map 如何删除map队列头 this.map.delete(this.map.keys().next().value)
var LRUCache = (capacity) => {
  this.capacity = capacity;
  this.map = new Map();
}
LRUCache.prototype.get = (key) => {
  if (this.map.get(key)) {
    let temp = this.map.get(key);
    // map 有前后的顺序
    this.map.delete(key)
    this.map.set(key, temp)
    return temp;
  } else {
    return -1;
  }
}
LRUCache.prototype.put = (key, value) => {
  if (this.map.get(key)) {
    this.map.delete(key) // 先删除变为最新
  }
  this.map.set(key, value)
  if (this.map.size > this.capacity) {
    this.map.delete(this.map.keys().next().value)
  }
}


